Tulane University, 2025
A sample
A Reconstruction
Source: Kyoto City Official Traval Guide
The City of Berlin
Q: How to draw the map of the city from a noisy point-cloud of GPS locations?
Source: mapconstruction.org
Shape: A Shape is modeled as a metric space (X,dX)(X,d_X)
Sample: A finite metric space (S,dS)(S,d_S) close to XX
Goal: Infer the topology of XX from SS.
Estimate only the Betti numbers—number of connected components, cycles, voids, etc—of XX
construct a topological space X̂\widehat{X} from SS to retain the topology of XX in some appropriate sense
a metric space (X,dX)(X,d_X)
a scale β>0\beta>0
ℛβ(X)\mathcal{R}_\beta(X) is an abstract simplicial complex
V = []; { const height = "450px"; const container = d3.create("div").style("position", "relative"); let svg = container .append("svg") .attr("class", "canvas") .style("margin-left", "15px") .style("width", "90%") .style("height", height) .style("border", "0.5px solid #eee"); const triangles = svg.append("g").attr("class", "triangles"); const edges = svg.append("g").attr("class", "edges"); const vertices = svg.append("g").attr("class", "vertices"); // scale container .append("div") .style("width", "15px") .style("height", height) .style("background", "#eee") .style("position", "absolute") .style("top", "0") .style("bottom", "0") .append("div") .style("width", "100%") .style("height", scale + "px") .style("background", "steelblue"); container .append("div") .style("margin-left", "12px") .style("width", height) .style("display", "inline-block") .style("text-align", "center") .style("transform", "rotate(-90deg)") .style("transform-origin", "top left") .html(tex`\beta`.outerHTML); drawRips(svg, sc.rips(V, scale, 2)); svg.on("click", (e) => { const coord = d3.pointer(e); V.push(coord); drawRips(svg, sc.rips(V, scale, 2)); }); return container.node(); }
import { slider } from "@jashkenas/inputs" sc = require("https://cdn.jsdelivr.net/npm/@tdajs/simplicial-complex@1.2.1/dist/min.js")
drawRips = function (svg, rips) { if (rips.simplices[2]) { svg.selectAll(".triangle") .data(rips.simplices[2]) .join("path") .attr("class", "triangle") .attr("d", (d) => d3.line()(d.map((v) => V[v]))) .attr("fill", "lightgreen") .attr("stroke", "none") .attr("opacity", "0.3"); } if (rips.simplices[1]) { svg.selectAll(".edge") .data(rips.simplices[1]) .join("path") .attr("class", "edge") .attr("d", (d) => d3.line()(d.map((v) => V[v]))) .attr("stroke", "green").attr("stroke-width", "2"); } svg.selectAll(".vertex") .data(V) .join("circle") .attr("class", "vertex") .attr("class", "vertex") .attr("fill", "white") .attr("cx", (d) => d[0]) .attr("cy", (d) => d[1]) .attr("r", "2px") .on("mouseover", function () { d3.select(this).attr("fill", "green").attr("r", "10px"); }) .on("mouseout", function () { d3.select(this).attr("fill", "white").attr("r", "2px"); }); return svg; }
viewof scale = Inputs.range([0, 300], { step: 1, value: 0, label: tex`\beta` }) viewof btn = Inputs.button("clear", { value: null, reduce: () => { V.length = 0; viewof scale.value = 0;viewof scale.dispatchEvent(new CustomEvent("input")); } })
—Metric structures of Riemann & non-Riemann Spaces, page100
Let XX be a length metric space…given by ε\varepsilon-nets Xε0X_\varepsilon^{0} in XX which Hausdorff converges XX…
…One can turn such a space into a path metric space, namely a graph Xε1⊂XX_\varepsilon^{1}\subset X with Xε0X_\varepsilon^{0} as its vertex set, and where two points xx and yy in Xε1X_\varepsilon^{1} within distance δ≤δε\delta\leq\delta_\varepsilon joined by an edge of length δ\delta.
…fll in the small triangles of edges in the graph Xε1X_\varepsilon^{1} by actual 22-dimensional triangles to obtain Xε2⊂XX_\varepsilon^{2}\subset X, then π1(Xε2)=π1(X)\pi_1(X_\varepsilon^{2})=\pi_1(X) for ε,δε→0\varepsilon,\delta_\varepsilon\to0 with ε/δε→∞\varepsilon/\delta_\varepsilon\to\infty.
Hausmann (1995)
For any closed Riemannian manifold MM and 0<β<ρ(M)0<\beta<\rho(M), the Vietoris–Rips complex ℛβ(M)\mathcal{R}_\beta(M) is homotopy equivalent to MM.
{ const svg = d3.create('svg').attr('viewBox', [-width/2, -600, width, 1200]); svg .append('circle') .attr('cx', '0') .attr('cy', '0') .attr('r', 500) .style('fill', 'none') .style('stroke-width', 10) .style('stroke', 'lightgray'); const arc = d3.arc() .innerRadius(490) .outerRadius(510) .startAngle(-rad * Math.PI * 2) .endAngle(rad * Math.PI * 2); svg.append("path") .attr("class", "arc") .attr("d", arc) .attr("fill", rad <= 0.25 ? "#3be57f" : "#bb473f"); svg.append('circle') .attr('cx', 0) .attr('cy', -500) .attr('r', 20) .style('fill', '#3be57f') return svg.node(); }
viewof rad = Inputs.range([0, 0.5], { step: 0.01, value: 0, label: '' })
Hausmann’s Curious Question
What about the Vietoris–Rips complex of a finite, dense subset S⊂MS\subset M?
Gromov–Hausdorff Distance:
Latschev (2001)
Every closed Riemannian manifold MM has an ϵ0>0\epsilon_0>0 such that for any 0<β≤ϵ00<\beta\leq\epsilon_0 there exists some δ>0\delta>0 so that for any sample SS: dGH(S,M)≤δ⟹ℛβ(S)≃M. d_{GH}(S,M)\leq\delta\implies \mathcal R_\beta(S)\simeq M.
the threshold ϵ0=ϵ0(M)\epsilon_0=\epsilon_0(M) depends solely on the geometry of MM. But the theorem did not say how!
δ=δ(β)\delta=\delta(\beta) is a function (a fraction in practice) of β\beta.
The result is qualitative
Nonetheless, the result provides a promising answer to Hausmann’s question, and more!
Metric Graph Reconstruction [J. Appl. & Comp. Top., Majhi (2023)]
Let (G,dG)(G,d_G) be a compact, path-connected metric graph, (S,dS)(S,d_S) a metric space, and β>0\beta>0 a number such that 3dGH(G,S)<β<34ρ(G).3d_{GH}(G,S)<\beta<\frac{3}{4}\rho(G). Then, ℛβ(S)≃G\mathcal R_\beta(S)\simeq G.
The result is quantitative
ϵ0=34ρ(G)\epsilon_0=\frac{3}{4}\rho(G)
δ=13β\delta=\frac{1}{3}\beta
The constants are not optimal!
Riemannian Manifold Reconstruction [SoCG’24, DCG, Majhi (2024)]
Let MM be a closed, connected Riemannian manifold. Let (S,dS)(S,d_S) be a compact metric space and β>0\beta>0 a number such that 1ξdGH(M,S)<β<11+2ξmin{ρ(M),π4κ} \frac{1}{\xi}d_{GH}(M,S)<\beta<\frac{1}{1+2\xi}\min\left\{\rho(M),\frac{\pi}{4\sqrt{\kappa}}\right\} for some 0<ξ≤1/140<\xi\leq1/14. Then, ℛβ(S)≃M\mathcal R_\beta(S)\simeq M.
κ\kappa is an upper bound on the sectional curvatures of MM
For ξ=114\xi=\frac{1}{14}:
ϵ0=78min{ρ(M),π4κ}\epsilon_0=\frac{7}{8}\min\left\{\rho(M),\frac{\pi}{4\sqrt{\kappa}}\right\}
δ=β14\delta=\frac{\beta}{14}
Euclidean Submanifold Reconstruction (Majhi 2024)
Let M⊂ℝNM\subset\mathbb R^N be a closed, connected submanifold. Let S⊂ℝNS\subset\mathbb R^N be a compact subset and β>0\beta>0 a number such that 1ξdH(M,S)<β<3(1+2ξ)(1−14ξ)8(1−2ξ)2τ(M) \frac{1}{\xi}d_{H}(M,S)<\beta<\frac{3(1+2\xi)(1-14\xi)}{8(1-2\xi)^2}\tau(M) for some 0<ξ<1/140<\xi<1/14. Then, ℛβ(S)≃M\mathcal R_\beta(S)\simeq M.
τ(M)\tau(M) is the reach of MM
For ξ=128\xi=\frac{1}{28}:
ϵ0=3151352τ(M)\epsilon_0=\frac{315}{1352}\tau(M)
δ=β28\delta=\frac{\beta}{28}
Length space: A metric space with an instrinsic metric
Geodesically complete: a pair can be joined by a length-minimizing path
geodesic triangles are “slimmer” than corresponding “model triangles” in a standard space of constant curvature κ\kappa.
Examples:
Quantitative Lastchev’s Theorem for CAT(κ)\mathrm{CAT}(\kappa) Spaces (Komendarczyk, Majhi, and Tran 2024)
ε\varepsilon-path Metric:
Fix an ε>0\varepsilon>0, proportional to dH(S,X)d_H(S,X)
For any two sample points a,b∈Sa,b\in S, define dSε(a,b)d_S^\varepsilon(a,b) to be the shortest distance when hopping over the points of SS with a step size ≤ε\leq\varepsilon.
Euclidean Subsets (Komendarczyk, Majhi, and Tran 2024)
Let XX be a geodesic subspace of ℝN\mathbb R^N. Let ξ∈(0,1)\xi\in\left(0,1\right) and β>0\beta>0 be fixed numbers. 0<ε≤β0<\varepsilon\leq\beta such that δβε(X)≤1+(ξ1+ξ)\delta^\varepsilon_{\beta}(X)\leq1+\left(\frac{\xi}{1+\xi}\right), then for any compact subset S⊂ℝNS\subset\mathbb R^N with dH(X,S)<12ξεd_H(X,S)<\frac{1}{2}\xi\varepsilon, we have ℛβε(S)≃X\mathcal{R}_\beta^\varepsilon(S)\simeq X.
Geometric Reconstruction (Komendarczyk, Majhi, and Mitra 2025)
Let G⊂ℝ2G \subset \mathbb{R}^2 a graph. Fix any ξ∈(0,1−Θ6)\xi\in\left(0,\frac{1-\Theta}{6}\right). For any positive β<min{Δ(G),ℓ(G)12}\beta<\min\left\{\Delta(G),\frac{\ell(G)}{12}\right\}, choose a positive ε≤(1−Θ)(1−Θ−6ξ)12β\varepsilon\leq\frac{(1-\Theta)(1-\Theta-6\xi)}{12}\beta such that δβε(G)≤1+2ξ1+ξ\delta^{\varepsilon}_{\beta}(G)\leq\frac{1+2\xi}{1+\xi}. If S⊂ℝ2S\subset \mathbb R^2 is compact and dH(G,S)<12ξεd_H(G,S)<\tfrac{1}{2}\xi\varepsilon, then the shadow sh(ℛβε(S))sh(\mathcal R_\beta^\varepsilon(S)) is homotopy equivalent to GG. Moreover, dH(sh(ℛβε(S)),G)<(β+12ξε)d_H(sh(\mathcal R_\beta^\varepsilon(S)),G)<\left(\beta+\frac{1}{2}\xi\varepsilon\right).